package practise;

public class Test {

}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
     //判断两颗二叉树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //使用前序遍历
        if(p==null && q!=null || p!=null && q==null) {
            return false;
        }
        if(p==null && q==null) {
            return true;
        }
        if(p.val!=q.val) {
            return false;
        }
        //代码可以改写为：
        //return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        boolean ret1 = isSameTree(p.left,q.left);
        if(ret1) {
            boolean ret2 = isSameTree(p.right,q.right);
            return ret2;
        } else{
            return false;
        }
    }

    //判断subRoot是不是root的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        /**
         先判断当前根是否是subRoot
         */
        //当root走到null时需要对其进行判断
        if(root == null) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(!isSubtree(root.left,subRoot)) {
            return isSubtree(root.right,subRoot);
        } else {
            return true;
        }
    }

     //翻转二叉树
     public TreeNode invertTree(TreeNode root) {
         if(root == null) {
             return null;
         }
         TreeNode tmp = root.left;
         root.left = root.right;
         root.right = tmp;
         invertTree(root.left);
         invertTree(root.right);
         return root;
     }

     public void invertTree() {

     }
 }


